package 算法练习;

import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月16日 上午9:11:30 
* @Description：
* 
给定两个字符串。
定义三种操作：
1.插入一个字符
2.修改一个字符
3.删除一个字符
求最少几步操作使得第一个字符串变成第二个字符串。
例如：第一个字符串lighten,第二个字符串fighting
fighten (l->f) 修改
fightin (e->i) 修改
fighting (->g) 插入
一共三步
*/

/*
 * 这就是典型的动态规划
 * 记dp[i][j]表示i和j相等所需要的修改次数
 * 那么当a[i]==b[i]时，dp[i][j]=dp[i-1][j-1]
 * 当两者不相等的时候，考虑修改的三种情况
 *   1.把第i位删除，那就说明第i-1位和第i位是相等的，有dp[i][j]=min(dp[i-1][j]+1,dp[i][j])
 *   2.在第i位前面添加一个数，那就说明第i位和第i-1位是相等的，有dp[i][j]=min(dp[i][j-1]+1,dp[i][j])
 *   3.修改第i位，那就说明第i-1和第j-1是相等的，有dp[i][j]=min(dp[i-1][j-1],dp[i][j])
 *   
 */


public class 最短编辑距离 {
	
	/**
     * 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
     *
     * 你可以对一个单词进行如下三种操作：
     *
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String word1 = scanner.nextLine();
        String word2 = scanner.nextLine();
        int n = word1.length();
        int m = word2.length();
        int[][] dp = new int[n + 1][m + 1];
        
        for (int i = 0; i <= n; ++i) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= m; ++i) {
            dp[0][i] = i;
        }
        
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}
